#include <stdio.h>
#include <omp.h>
#include <time.h>
#include <stdlib.h>
#include "fun_group.h"

void quickSort_parallel_internal(int *array, int left, int right, int cutoff)
{

	int i = left, j = right;
	int tmp;
	int pivot = array[(left + right) / 2];

	{
		/* PARTITION PART */
		while (i <= j)
		{
			while (array[i] < pivot)
				i++;
			while (array[j] > pivot)
				j--;
			if (i <= j)
			{
				tmp = array[i];
				array[i] = array[j];
				array[j] = tmp;
				i++;
				j--;
			}
		}
	}

	if (((right - left) < cutoff))
	{
		if (left < j)
		{
			quickSort_parallel_internal(array, left, j, cutoff);
		}
		if (i < right)
		{
			quickSort_parallel_internal(array, i, right, cutoff);
		}
	}
	else
	{
#pragma omp task
		{
			quickSort_parallel_internal(array, left, j, cutoff);
		}
#pragma omp task
		{
			quickSort_parallel_internal(array, i, right, cutoff);
		}
	}
}

void quickSort_parallel(int *array, int lenArray, int numThreads)
{

	int cutoff = 1000;

	#pragma omp parallel num_threads(numThreads)
	{
		#pragma omp single nowait
		{
			quickSort_parallel_internal(array, 0, lenArray - 1, cutoff);
		}
	}
}

int main()
{
	double parallel_start_time, parallel_end_time,
		serial_end_time, serial_start_time;

	// 产生排序数据
	int size_list[33] = {1e3, 1e4, 2e4, 3e4, 4e4, 5e4, 6e4, 7e4, 8e4, 
		1e5, 2e5, 3e5, 4e5, 5e5, 6e5, 7e5, 8e5,
		1e6, 2e6, 3e6, 4e6, 5e6, 6e6, 7e6, 8e6,  
		1e7, 2e7, 3e7, 4e7, 5e7, 6e7, 7e7, 8e7, 
	};
	int DataSize = 1e3;
	int proc_num = 12;
	for (int i = 0; i < 25; i++)
	{
		for (int j = 2; j < 13; j++)
		{
			int DataSize = size_list[i]; // set data size
			int proc_num = j;			 // set the number of processes
			omp_set_num_threads(proc_num);
			int SIZE = sizeof(int) * DataSize;
			int *data = (int *)malloc(SIZE);
			int *dataCopy = (int *)malloc(SIZE);
			CreateData(data, DataSize);
			for (int i = 0; i < DataSize; ++i)
				dataCopy[i] = data[i];

			// 并行冒泡排序
			parallel_start_time = omp_get_wtime();
			quickSort_parallel(data, DataSize, omp_get_thread_num());
			#pragma omp parallel
			{
				#pragma omp barrier				   // 等待所有进程结束
			} parallel_end_time = omp_get_wtime(); // 获取结束时间
			for (int i = 0; i < 100; i++)
			{
				printf("%d ", data[i]);
			}
			puts("... ...");

			// 串行冒泡排序
			serial_start_time = omp_get_wtime();
			serial_QuickSort(dataCopy, 0, DataSize);
			serial_end_time = omp_get_wtime();

			char sort_name[] = "opm_quicksort";
			char filepath[] = "result_quick_omp.txt";
			put_time_info(filepath, sort_name, DataSize, proc_num, parallel_start_time, parallel_end_time, serial_start_time, serial_end_time);
		}
	}
	return 0;
}
